// 给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。

// 示例：



// 输入：
// {"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

// 解释：
// 节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
// 节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
// 节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
// 节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
 

// 提示：

// 节点数介于 1 到 100 之间。
// 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
// 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
// 必须将给定节点的拷贝作为对克隆图的引用返回。
// Definition for a Node.

#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

// DFS
class Solution1 {
public:
    Node* cloneGraph(Node* node) {
        unordered_map<Node*, Node*> hash{};
        return func(node, hash);
    }
    Node* func(Node* node, unordered_map<Node*, Node*>& hash) {
        if (!node) return nullptr;
        if (hash.count(node)) return hash[node]; // 当前节点已经克隆过
        Node* new_node = new Node(node->val, vector<Node*>{});
        hash[node] = new_node;
        for (Node* neighbor : node->neighbors) {
            new_node->neighbors.push_back(func(neighbor, hash));
        }
        return new_node;
    }
};

// BFS
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        unordered_map<Node*, Node*> hash{};
        queue<Node*> q{{node}};
        Node* new_node = new Node(node->val, vector<Node*>{});
        hash[node] = new_node;
        while (!q.empty()) {
            Node* t = q.front();
            q.pop();
            for (Node* neighbor : t->neighbors) {
                if (!hash.count(neighbor)) {
                    hash[neighbor] = new Node(neighbor->val, vector<Node*>{});
                    q.push(neighbor);
                }
                hash[t]->neighbors.push_back(hash[neighbor]);
            }
        }
        return new_node;
    }
};

/* 深度优先搜索
时间复杂度：O(N)
空间复杂度：O(N)
*/
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (nullptr == node) {
            return nullptr;
        }
        if (visited.find(node) != visited.end()) { // 访问过
            return visited[node]; // 将克隆节点返回
        }
        Node* cloneNode = new Node(node->val);
        visited[node] = cloneNode;
        for (Node* neighbor : node->neighbors) {
            cloneNode->neighbors.emplace_back(cloneGraph(neighbor));
        }
        return cloneNode;
    }
private:
    unordered_map<Node*, Node*> visited{};
};

/* 广度优先搜索
时间复杂度：O(N)
空间复杂度：O(N)
*/
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (nullptr == node) {
            return nullptr;
        }
        unordered_map<Node*, Node*> visited{}; // 存放的是原节点与对应的clone节点
        queue<Node*> q{};
        q.push(node);
        visited[node] = new Node(node->val);
        while (!q.empty()) {
            Node* temp = q.front();
            q.pop();
            for (Node* neighbor : temp->neighbors) {
                if (visited.find(neighbor) == visited.end()) { // 之前没有clone过该节点
                    visited[neighbor] = new Node(neighbor->val);
                    q.push(neighbor);
                }
                visited[temp]->neighbors.emplace_back(visited[neighbor]);
            }
        }
        return visited[node];
    }
};
